package com.wq.sort;

/**
 * @Author: wangqiang20995
 * @Date:19-3-10
 * @Description:
 * @Resource:
 */
public class MergeSort extends BaseSort {

    public MergeSort(int size) {
        super(size);
    }

    public void mergeSort() {
        int high = array.length - 1;
        int low = 0;
        int[] sortCopy = new int[array.length];

        recursionMergeSort(sortCopy, low, high);

        super.array = sortCopy;
    }

    private void recursionMergeSort(int[] sortCopy, int low, int high) {
        if (low == high) {
            return;
        } else {
            int mid = (low + high) / 2;
            recursionMergeSort(sortCopy, low, mid);
            recursionMergeSort(sortCopy, mid + 1, high);
            //此时两边都已经是有序，进行merge
            mergeArray(sortCopy, low, mid, high);
        }
    }

    private void mergeArray(int[] sortCopy, int low, int mid, int high) {
        int i = low, j = mid + 1, k = 0;
        int currentNumber = high - low + 1;
        while (i <= mid && j <= high) {
            if (array[i] < array[j]) {
                sortCopy[k++] = array[i++];
            } else {
                sortCopy[k++] = array[j++];
            }
        }

        while (i <= mid) {
            sortCopy[k++] = array[i++];
        }

        while (j <= high) {
            sortCopy[k++] = array[j++];
        }

        //将本次合并的结果，更新到array原数组中去
        for(int index = 0;index<currentNumber;index++){
            array[low++] = sortCopy[index];
        }
    }

    public static void main(String args[]){
//        mergeDemo();
        MergeSort mergeSort = new MergeSort(1000000);
        mergeSort.printArray(false);
        long start =  System.currentTimeMillis();
        mergeSort.mergeSort();
        long end = System.currentTimeMillis();

        System.out.println("cost-->" + (end - start));

        mergeSort.printArray(false);
    }

    private static void mergeDemo() {
        int small[] = {2, 4, 6, 7, 9};
        int big[] = {1, 4, 5, 8, 10, 42, 45};

        int[] merge = new int[small.length + big.length];

        int i = 0, j = 0, k = 0;
        while (i < small.length && j < big.length) {
            if (small[i] < big[j]) {
                merge[k++] = small[i++];
            } else {
                merge[k++] = big[j++];
            }
        }

        while (i < small.length) {
            merge[k++] = small[i++];
        }

        while (j < big.length) {
            merge[k++] = big[j++];
        }

        for (int num = 0; num < merge.length; num++) {
            System.out.printf("%d\t", merge[num]);
        }
    }
}
